This invention generally relates to encoding and decoding an information signal. In particular, the invention relates to a method for information signal encoding and decoding using variable-length combinatorial and Huffman codes.
Methods for coding an information signal form the basis for a significant amount of speech, audio, image and video transmissions through communication channels or from storage devices. Digital speech encoding standards for code division multiple access (CDMA) mobile phone systems, for example, are described in the approved specification (ANSI/TIA/EIA-95-B-1999) entitled xe2x80x9cMobile Stationxe2x80x94Base Station Compatibility Standard for Wideband Spread Spectrum Cellular Systemsxe2x80x9d (1999), published by the Electronic Industries Association (EIA), 2500 Wilson Blvd., Arlington, Va., 22201. A variable rate speech codec, and specifically a Code Excited Linear Prediction (CELP) codec for use in communication systems compatible with IS-95, is defined in the document (TIA/EIA/IS-127) entitled xe2x80x9cEnhanced Variable Rate Codec, Speech Service Option 3 for Wideband Spread Spectrum Digital Systemsxe2x80x9d (1997), published by the Electronics Industries Association (EIA), 2500 Wilson Blvd., Arlington, Va., 22201.
A method for encoding a speech signal using factorial packing (FP) is described in xe2x80x9cFactorial Packing Method and Apparatus for Information Codingxe2x80x9d, U.S. Pat. No. 6,236,960 by Peng et al., issued May 22, 2001. This speech coder utilizes four characteristics to uniquely describe any given pulse combination: number of degenerate pulses, signs of pulses, positions of non-zero pulses, and pulse magnitudes. A four-stage iterative classification of the pulse combination is performed, starting with the number of non-zero pulses and then determining the remaining parameters. The most significant bits in FP have most of the information about the number of non-zero pulses, while the least significant bits have primarily sign information showing a partial segregation of constituent information in FP. There is no complete segregation in this method, and therefore an error in the central bits does not always ensure that the number of degenerate pulses can be decoded correctly. Factorial packing is an example of an enumeration method, where indices are assigned to the pulse configurations. The codeword that is generated with this method, however, has no well-defined bit fields that represent the pulse characteristics.
The pyramid vector quantization (PVQ) method, as described by Fischer, xe2x80x9cA Pyramid Vector Quantizerxe2x80x9d, IEEE Transactions on Information Theory, Vol. IT-32, July 1986, pp. 568-583, is another example of an enumeration method. The enumeration technique may be very sensitive to bit errors. Hung et al., in the article xe2x80x9cError-Resilient Pyramid Vector Quantization for Image Compressionxe2x80x9d, IEEE Transactions on Image Processing, Vol. 7, October 1998, pp. 1373-1386, proposed some PVQ enumeration methods that are less sensitive to bit errors than those proposed by Fischer. Two of their proposed enumeration methods, Conditional Product Code (CPC) and Conditional Product-Product Code (CPPC), were found to be robust to bit errors when used for representing Discrete Cosine Transform (DCT) coefficients in image compression. FP may be considered a variant of CPC. FP and CPC achieve robust performance by xe2x80x9cpartial segregationxe2x80x9d of information present in a pulse configuration. The CPPC method has more segregation of constituent information, although it also does not ensure complete segregation. The comparisons between CPPC and CPC indicate that the CPPC method may be more robust to bit errors, suggesting that increasing information segregation may increase robustness. With complete information segregation, none of the bits in the codeword is affected by more than one of the constituents. It would be preferred that addition and multiplication functions would not be used to combine constituent codewords into a complete codeword, as these operations may add to the complexity of the coding process, and also tend to decrease segregation. The codeword should be formed by a concatenation of the constituent codewords, thus maintaining complete information segregation for higher error resilience.
A method for coding an information signal based on parameters inherent to the information signal is described in xe2x80x9cMethod and Apparatus for Coding an Information Signalxe2x80x9d, U.S. Pat. No. 6,141,638, W. Peng and J. Ashley, issued Oct. 31, 2000. The method selects one of a plurality of configurations based on predetermined parameters related to the information signal, each of the plurality of configurations having a codebook; and searches the codebook over the length of an excitation vector which is shorter than a sub-frame length, to determine a codebook index from the codebook corresponding to the selected configuration; and transmits the predetermined parameters and the codebook index to a destination.
A code-excited linear prediction (CELP) technique is described in the paper by James P. Ashley, Edgardo M. Cruz-Zeno, Udar Mittal and Weimen Peng, xe2x80x9cWideband Coding of Speech Using a Scalable Pulse Codebookxe2x80x9d, Proceedings IEEE Workshop on Speech Coding 2000, Lake Delavan, Wis., September, 2000. The technique is scalable to a wide range of bit rates. The method improves the coding efficiency of multiple pulse ACELP tracks in wideband speech coding. The method was also shown to be extendable beyond Algebraic Code-Excited Linear Predictive (ACELP) speech coders, such that the standard track constraints are eliminated while still achieving high quality speech.
Three principal figures of merit for speech encoding methods include: the bit rate, the quality of the reconstructed speech, and the amount of computation necessary to encode and decode the speech or similar information signal. Improvements may be made for a fixed bit rate by using improved codes to increase the computational efficiency of the encoder, and incorporating techniques for improved error resiliency of the transmitted codewords to achieve higher quality speech transmission.
It is an object of this invention, therefore, to improve upon the computational complexity of indexed coding and decoding, to provide higher error resiliency associated with factorial packing methods, and to overcome the deficiencies and obstacles described above.
One aspect of the invention provides a method of coding an information signal. An information signal may be represented by a sequence of pulses. A plurality of pulse parameters based on the sequence of pulses may be determined, with one of the pulse parameters corresponding to the number of non-zero pulse positions in the sequence of pulses. The non-zero pulse parameter may be coded using a variable-length codeword.
Parameters may represent the number of non-zero pulses in the sequence of pulses, the location or positions of the non-zero pulses, the magnitudes of the non-zero pulses, and the phase or signs of the non-zero pulses.
The coded pulse parameters may be assembled into a sequence of codewords. The first codeword may represent the number of non-zero pulses in the sequence of pulses. The non-zero pulse parameter may be coded using a variable-length Huffman code. The pulse position parameter ma be coded using a combinatorial expression related to the total number of available positions and the number of non-zero positions in the sequence of pulses. The combinatorial function may be accessed using a medium memo storage routine (MMSR). The combinatorial function may be accessed using a smallest memory storage routine (SMSR). The pulse magnitude parameter may coded using a combinatorial function related to the sum of the pulse magnitude and the number of non-zero pulse positions in the sequence of pulses. The combinatorial function may be accessed using a medium memory storage routine. The combinatorial function may be accessed using a smallest memory storage routine. The pulse magnitude parameter may contain a predetermined sum of pulse magnitudes in the sequence of pulses. The pulse phase parameter may represent the signs or phases of the non-zero pulse positions in the sequence of pulses.
The information signal may comprise a time-domain signal. The information signal may comprise a frequency-domain signal. The information signal may include a speech signal, a transformed speech signal, an audio signal, a transformed audio signal, an image signal, a transformed image signal, a video signal, and a transformed video signal.
Another aspect of the current invention is a system for coding an information signal. The coder may comprise a means for representing the information signal by a sequence of pulses; a means for determining a plurality of pulse parameters based on the sequence of pulses including a non-zero pulse parameter corresponding to a number of non-zero pulse positions in the sequence of pulses; and a means for coding the non-zero pulse parameter using a variable-length codeword. The system may further comprise a means for assembling the coded pulse parameters into a sequence of codewords.
Another aspect of the current invention is a computer usable medium including a program for coding an information signal. The program may contain computer program code for representing the information signal by a sequence of pulses; computer program code for determining a plurality of pulse parameters based on the sequence of pulses, including a non-zero pulse parameter corresponding to a number of non-zero pulse positions in the sequence of pulses; and computer program code for coding the non-zero pulse parameter using a variable-length codeword.
The program may also include computer program code for assembling the coded parameters into a sequence of codewords.
Another aspect of the current invention is a method of decoding an information signal. A plurality of codewords may be received from a source. A set of characteristics of the information signal may be determined based in part on a variable-length codeword representing the number of non-zero pulse positions contained in the information signal. The information signal may be decoded based on the set of characteristics. The set of characteristics may include the positions or locations of non-zero pulses, pulse magnitudes and pulse phases.
The information signal may be a speech signal, a transformed speech signal, an audio signal, a transformed audio signal, an image signal, a transformed image signal, a video signal, or a transformed video signal. The information signal may comprise a time-domain signal, or the information signal may comprise a frequency-domain signal. The codewords may be received from a communications channel. The codewords may be received from a storage device.
Another aspect of the current invention is a system for decoding an information signal. The information decoding system may include a means for receiving a plurality of codewords from a source, a means for determining a set of characteristics of the information signal based in part on a variable-length codeword representing the number of non-zero positions contained in the information signal, and a means for decoding the information signal based on the set of characteristics.
Another aspect of the current invention is a computer usable medium including a program for decoding an information signal. The program may contain computer program code for receiving a plurality of codewords from a source; computer program code for determining a set of characteristics of the information signal based in part on a variable-length codeword representing the number of non-zero pulse positions contained in the information signal; and computer program code for decoding the information signal based on the set of characteristics.
The aforementioned, and other features and advantages of the invention will become further apparent from the following detailed description of the presently preferred embodiments, read in conjunction with the accompanying drawings. The detailed description and drawings are merely illustrative of the invention rather than limiting, the scope of the invention being defined by the appended claims and equivalents thereof.